package 二叉树;

public class No108将有序数组转换为二叉搜索树 {

    /**
     * 将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。
     *
     * 本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
     *
     * 示例:
     *
     * 给定有序数组: [-10,-3,0,5,9],
     *
     * 一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：
     *
     *       0
     *      / \
     *    -3   9
     *    /   /
     *  -10  5
     */

    private int arr[];

    public TreeNode sortedArrayToBST(int[] nums) {
        //从中间开始截断, (left+right)/2 取为当前节点
        if(nums==null||nums.length==0)
            return null;
        arr=nums;
        TreeNode resultNode = dg(0, arr.length-1);
        return resultNode;
    }

    private TreeNode dg(int left,int right){
        if(left>right)
            return null;
        int mid=(right-left)/2+left;
        TreeNode treeNode=new TreeNode(arr[mid]);
        //mid用了就把它去掉
        treeNode.left=dg(left,mid-1);
        treeNode.right=dg(mid+1,right);
        return treeNode;
    }

}
